package work.tree;

import work.TreeNode;

public class Problem114 {
    public void flatten(TreeNode root) {
        dfs(root);
    }
    private TreeNode dfs(TreeNode root) {
        if (root == null) return null;
        //代表着的是左子树的尾节点
        TreeNode leftTail = dfs(root.left);
        //右子树的尾节点
        TreeNode rightTail = dfs(root.right);

        if (leftTail != null) {
            leftTail.right = root.right;
            root.right = root.left;
            root.left = null;
        }
        if (rightTail != null) {
            return rightTail;
        } else if (leftTail != null) {
            return leftTail;
        } else {
            return root;
        }
    }

}
